class Task40Partition:
    def run(self, array, k):
        target = k - 1
        start = 0
        end = len(array)
        index = self.partition(array, start, end)
        while index != target:
            if index < target:
                start = index + 1
            else:
                end = index
            index = self.partition(array, start, end)
        return array[:index + 1]

    def partition(self, array, start, end):
        k = start
        x = array[k]
        array[k], array[end - 1] = array[end - 1], array[k]
        i = start - 1
        for j in range(start, end):
            if array[j] < x:
                i += 1
                array[i], array[j] = array[j], array[i]
        i += 1
        array[i], array[end - 1] = array[end - 1], array[i]
        return i


class Task40Heap:
    def run(self, array, k):
        buffer = array[:k]
        self.build_max_heap(buffer)

        for num in array[k:]:
            if num < buffer[0]:
                buffer[0] = num
                self.sift_down(buffer, 0)

        return buffer

    def build_max_heap(self, array):
        n = (len(array) // 2) - 1
        for index in reversed(range(n + 1)):
            self.sift_down(array, index)

    def sift_down(self, array, index):
        left_index = index * 2 + 1
        right_index = index * 2 + 2
        max_index = index
        if left_index < len(array) and array[left_index] > array[max_index]:
            max_index = left_index
        if right_index < len(array) and array[right_index] > array[max_index]:
            max_index = right_index
        if max_index != index:
            array[max_index], array[index] = array[index], array[max_index]
            self.sift_down(array, max_index)
